package leetcode_core.leetcode_6;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年01月31日 20:55
 */
public class CountRangeSum {
    private int count = 0;
    private long[] memo;
    private int lower;
    private int upper;
    public int countRangeSum(int[] nums, int lower, int upper) {
        int n = nums.length;
        long[] preSum = new long[n+1];
        this.lower = lower;
        this.upper = upper;
        for(int i = 0;i<n;i++){
            preSum[i+1] = preSum[i-1]+nums[i];
        }
        sort(preSum,0,n);
        return count;
    }

    //题目是允许有[0,0存在的]
    private void sort(long[] nums,int lo,int hi){
        if(lo == hi){return;}
        //后序遍历
        int mid = lo + ((hi - lo) >> 1);
        sort(nums,lo,mid);
        sort(nums,mid+1,hi);
        merge(nums,lo,mid,hi);
    }

    private void merge(long[] nums,int lo,int mid,int hi){
        for(int i = lo;i<=hi;i++){
            memo[i] = nums[i];
        }
        //固定i
        int start = mid+1;
        int end = mid+1;
        for(int i = lo;i<=mid;i++){
            //然后检查
            while (start<= hi && nums[start]-nums[i]<lower){
                start++;
            }
            end = start;
            while (end<= hi && nums[end] - nums[i] >= upper){
                end++;
            }
            count += end - start;
        }
        //做排序
        int i = lo;
        int j = mid+1;
        for(int p = lo;p<=hi;p++){
            if(i == mid+1){
                nums[p] = memo[j++];
            }else if(j == hi+1){
                nums[p] = memo[i++];
            }else if(memo[i] < memo[j]) {
                nums[p] = memo[i++];
            }else{
                nums[p] = memo[j++];
            }
        }
    }
}
